8324. Интересная забава Юры

 

На уроке информатики Юре стало очень грустно, поэтому он придумал себе забаву.

В начале у него есть пустое множество. На каждом следующем этапе он загадывает число и проверяет, принадлежит ли оно множеству. Если число принадлежит множеству, Юра выкрикивает “Yes”. Если нет, он выкрикивает “No” и добавляет его в множество. Перед тем как загадать новое число, Юра выкрикивает количество элементов в множестве.

Учителю надоели крики Юрия, поэтому он заставил его написать программу, которая будет кричать вместо него. Но Юра не умеет программировать, поэтому попросил помощи у Вас.

 

Вход. В первой строке задано натуральное число n (1 ≤ n ≤ 105). В каждой из следующих n строк задано целое число, которое задумал Юра. Юра умеет загадывать числа только на промежутке от -109 до 109.

 

Выход. В отдельной строке выведите то, что выкрикивал бы Юра на каждый запрос.

 

Пример входа 1

Пример выхода 1

5

1

2

3

4

1

No 1

No 2

No 3

No 4

Yes 4

 

 

Пример входа 2

Пример выхода 2

3

1

1

1

No 1

Yes 1

Yes 1

 

 

РЕШЕНИЕ

структура данных set

 

Анализ алгоритма

В задаче следует промоделировать работу с множеством set. Пусть x – число, задуманное Юрой. Если x уже присутствует в множестве, выводим “Yes” и размер множества. Иначе добавляем x в множество, выводим “No” и размер множества.

 

Реализация алгоритма

Объявим множество s.

 

set<int> s;

 

Читаем количество запросов n.

 

scanf("%d",&n);

 

Последовательно обрабатываем n запросов.

 

for(i = 1; i <= n; i++)

{

 

Читаем число x, которое задумал Юра.

 

  scanf("%d",&x);

 

Если числа x нет в множестве s, то заносим его туда, выводим “No” и мощность множества.

 

  if(s.find(x) == s.end())

  {

    s.insert(x);

    printf("No %d\n",s.size());

  }

  else

 

Если число x присутствует в множестве s, то выводим “Yes” и мощность множества.

 

    printf("Yes %d\n",s.size());

}

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    TreeSet<Integer> s = new TreeSet<Integer>();

 

    int n = con.nextInt();

    for(int i = 0; i < n; i++)

    {

      int x = con.nextInt();

      if (s.contains(x))

        System.out.println("Yes " + s.size());

      else

      {

        s.add(x);

        System.out.println("No " + s.size());

      }

    }

    con.close();

  }

}  

 

Python реализация

Читаем количество запросов n.

 

n = int(input())

 

Объявим множество s.

 

s = set({})

 

Последовательно обрабатываем n запросов.

 

for _ in range(n):

 

Читаем число x, которое задумал Юра.

 

  x = int(input())

 

Если число x присутствует в множестве s, то выводим “Yes”.

 

  if x in s:

    print("Yes", end = ' ')

  else:

 

Если числа x нет в множестве s, то заносим его туда и выводим “No”.

 

    s.add(x)

    print("No", end = ' ')

 

После сообщения “Yes” или “No” выводим мощность множества.

 

  print(len(s))